Many processors include one or more memories integrated into the processor core. Such memories include cache structures, which are typically formed of static random access memory (SRAM), as well as read only memories (ROMs) such as microcode storage. Microcode is the lowest-level instructions that directly control a microprocessor. A single machine-language instruction typically translates into several microcode instructions. Microcode operates by using the programmability of microarchitectural components to enhance functionality, and to apply updates to an existing design (e.g., a processor design). In such a manner, die area, power consumption, and design cost may be kept under control.
However, recent trends have migrated more advanced functionality to microcode of a processor core. Many processor designs include thousands of lines of microcode, and microcode storage can consume up to 20% of the die area of a processor. The cost for microcode storage is especially acute where small footprint dies and reduced power consumption are required, such as in processors used in embedded applications. Thus, any reduction in microcode size directly translates to reduced cost and power consumption in processors. A current technique for reducing microcode size includes compressing the microcode.
One basic idea for compressing microcode is to identify a set of unique bit patterns that compose the microcode word and store these in a table with a unique short ID for each pattern in the original microcode word sequence. An improvement of this basic idea is the clustering algorithm. The clustering algorithm splits each microcode word into a number of sub-words so that the number of unique patterns for each sub-word is minimized. The clustering algorithm accomplishes this by grouping similar columns of microcode storage into clusters, so that the total microcode storage size reduction is maximized.
A current approach to determine cluster groupings is through a K-means-based algorithm. The K-means algorithm uses a distance metric between pairs of columns to determine which cluster the columns should be assigned to. Although the K-means algorithm finds reasonably good reductions in microcode size, the distance between columns does not directly relate to microcode size reductions. In other words, a good cluster identified by the K-means algorithm ensures that the difference between columns in a cluster is small, but this does not necessarily mean that the redundancy between the rows is the highest for maximal microcode size reduction. Therefore, a new clustering algorithm that does not rely on the distance between pairs of columns to identify the best cluster for microcode size reduction would be beneficial.